/*
 * @lc app=leetcode.cn id=111 lang=rust
 *
 * [111] 二叉树的最小深度
 */
// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
struct Solution;

// @lc code=start
use std::cell::RefCell;
use std::ops::Deref;
use std::rc::Rc;
impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        pruning(root)
    }
}

fn pruning(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut ans = i32::MAX;
    fn dfs(node: Option<&Rc<RefCell<TreeNode>>>, cnt: i32, ans: &mut i32) {
        if let Some(node) = node {
            let node = node.borrow();
            let cnt = cnt + 1;
            if cnt >= *ans {
                return; // 最优性剪枝
            }
            if node.left.is_none() && node.right.is_none() {
                *ans = cnt;
                return;
            }
            dfs(node.left.as_ref(), cnt, ans);
            dfs(node.right.as_ref(), cnt, ans);
        }
    }
    dfs(root.as_ref(), 0, &mut ans);
    if root.is_some() {
        ans
    } else {
        0
    }
}

// @lc code=end
pub fn min_depth_take_own(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(node) = root {
        let mut node = node.borrow_mut();
        if node.right.is_none() {
            return min_depth_take_own(node.left.take()) + 1;
        }
        if node.left.is_none() {
            return min_depth_take_own(node.right.take()) + 1;
        }
        return min_depth_take_own(node.left.take()).min(min_depth_take_own(node.right.take())) + 1;
    }
    0
}
fn borrow_solution(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(node) = root {
        let node_borrow = node.deref().borrow();
        let left = node_borrow.left.clone();
        let right = node_borrow.right.clone();
        match (left, right) {
            (None, None) => return 1,
            (None, Some(right)) => return 1 + borrow_solution(Some(right)),
            (Some(left), None) => return 1 + borrow_solution(Some(left)),
            (Some(left), Some(right)) => {
                return 1 + std::cmp::min(borrow_solution(Some(left)), borrow_solution(Some(right)))
            }
        }
    } else {
        return 0;
    }
}

mod tests {
    use super::*;
    // [2,null,3,null,4,null,5,null,6]
    #[test]
    fn test_1() {
        //     2
        // n       3
        //     n      4
        //         n     5
        //             n   6
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: 2,
            left: None,
            right: Some(Rc::new(RefCell::new(TreeNode {
                val: 3,
                left: None,
                right: Some(Rc::new(RefCell::new(TreeNode {
                    val: 4,
                    left: None,
                    right: Some(Rc::new(RefCell::new(TreeNode {
                        val: 5,
                        left: None,
                        right: Some(Rc::new(RefCell::new(TreeNode {
                            val: 6,
                            left: None,
                            right: None,
                        }))),
                    }))),
                }))),
            }))),
        })));
        assert_eq!(Solution::min_depth(root), 5);
    }
}
